include!("macros.rs");
pub mod error;

use error::{XErr, ZErr};
use rand::random;
use std::rc::{Rc, Weak};

pub trait Key: Clone + Eq + PartialEq + Ord + PartialOrd {}
impl<T: Clone + Eq + PartialEq + Ord + PartialOrd> Key for T {}

#[derive(Default)]
pub struct SkipList<K: Key, V> {
    max_height: usize,
    unit_siz: usize,
    layers: Vec<Layer<K, V>>,
}

struct Layer<K: Key, V> {
    node_cnt: usize, //节点总数
    head: Rc<Node<K, V>>,
}

pub struct Node<K: Key, V> {
    key: Rc<K>,
    value: Rc<V>,

    lower: Option<Rc<Node<K, V>>>,
    upper: Weak<Node<K, V>>,
    right: Option<Rc<Node<K, V>>>,
    left: Weak<Node<K, V>>,
}

impl<K: Key, V> SkipList<K, V> {
    pub fn default() -> SkipList<K, V> {
        Self::new(32, 4)
    }

    pub fn new(max_height: usize, mut unit_siz: usize) -> SkipList<K, V> {
        //有效值: 2 或 4
        unit_siz = unit_siz / 2 * 2;
        if unit_siz < 2 {
            unit_siz = 2;
        } else if unit_siz > 4 {
            unit_siz = 4;
        }

        SkipList {
            max_height,
            unit_siz,
            layers: vec![],
        }
    }

    /// 置新值
    pub fn put(&mut self, key: K, value: V) -> Result<(), XErr> {
        let key = Rc::new(key);
        let value = Rc::new(value);

        match self.locate(&key) {
            Ok(_) => Err(XErr::AlreadyExists),
            Err(ZErr::NotExists(None)) => {
                self.layers.push(Layer {
                    node_cnt: 1,
                    head: Rc::new(Node {
                        key,
                        value,
                        upper: Weak::new(),
                        lower: None,
                        left: Weak::new(),
                        right: None,
                    }),
                });
                Ok(())
            }
            Err(ZErr::NotExists(Some(mut adj))) => {
                let mut raw;
                let layer_num = self.gen_height(self.unit_siz);

                let mut new;
                let mut old = None;
                let mut i = 0;
                loop {
                    new = Rc::new(Node {
                        key: Rc::clone(&key),
                        value: Rc::clone(&value),
                        upper: Weak::new(),
                        lower: old.clone(),
                        left: Weak::new(),
                        right: None,
                    });

                    if let Some(mut old) = old {
                        chg!(old, upper, Rc::downgrade(&new), raw);
                        Self::upper_refresh(old);
                    }

                    if key > adj.key {
                        chg!(new, right, adj.right.clone(), raw);
                        chg!(new, left, Rc::downgrade(&adj), raw);

                        if let Some(right) = adj.right.as_ref() {
                            chg!(@Rc::clone(right), left, Rc::downgrade(&new), raw);
                        }
                        chg!(adj, right, Some(Rc::clone(&new)), raw);
                    } else {
                        chg!(new, right, Some(Rc::clone(&adj)), raw);
                        chg!(new, left, Weak::clone(&adj.left), raw);

                        if let Some(left) = Weak::upgrade(&adj.left) {
                            chg!(@left, right, Some(Rc::clone(&new)), raw);
                        } else {
                            debug_assert!(Rc::ptr_eq(&adj, &get!(self.layers, i).head));
                            get_mut!(self.layers, i).head = Rc::clone(&new); //无左邻, 一定是首节点
                        }
                        chg!(adj, left, Rc::downgrade(&new), raw);
                    }

                    get_mut!(self.layers, i).node_cnt += 1;
                    old = Some(new);
                    i += 1;

                    if i <= layer_num {
                        if let Some(upper) = Weak::upgrade(&adj.upper) {
                            adj = upper;
                        } else if layer_num >= self.layers.len() {
                            //顶层节点多于一个时, 才加层, 防止出现单线悬挂
                            if 1 < get!(self.layers, self.layers.len() - 1).node_cnt {
                                new = Rc::new(Node {
                                    key,
                                    value,
                                    upper: Weak::new(),
                                    lower: old.clone(),
                                    left: Weak::new(),
                                    right: None,
                                });

                                self.layers.push(Layer {
                                    node_cnt: 1,
                                    head: Rc::clone(&new),
                                });

                                let mut old = old.unwrap();
                                chg!(old, upper, Rc::downgrade(&new), raw);
                                Self::upper_refresh(old);
                            }
                            break;
                        }
                    } else {
                        //因新节点层数小于既有最高层数而中断,
                        //需要为最高的新节点更新父节点
                        chg!(@old.unwrap(), upper, Weak::clone(&adj.upper), raw);
                        break;
                    }
                }

                Ok(())
            }
            Err(e) => Err(e.into()),
        }
    }

    /// 删除已有节点
    pub fn del(&mut self, key: &K) -> Result<(), XErr> {
        let mut node = self.locate(key).map_err(XErr::from)?;

        //返回的一定是层级最高的匹配节点
        loop {
            if let Some(left) = Weak::upgrade(&node.left) {
                chg!(@left, right, node.right.clone());
            }

            if let Some(right) = node.right.as_ref() {
                chg!(@Rc::clone(right), left, Weak::clone(&node.left));
            }

            if let Some(lower) = node.lower.as_ref() {
                node = Rc::clone(lower);
            } else {
                break;
            }
        }

        let mut i = 0;
        loop {
            get_mut!(self.layers, i).node_cnt -= 1;

            if Rc::ptr_eq(&node, &get!(self.layers, i).head) {
                if let Some(left) = Weak::upgrade(&node.left) {
                    get_mut!(self.layers, i).head = left;
                } else if let Some(right) = node.right.as_ref() {
                    get_mut!(self.layers, i).head = Rc::clone(right);
                } else {
                    //被删节点是顶层唯一节点, 将其上各层全部清空
                    self.layers.drain(i..);
                    break;
                }
            }

            if let Some(upper) = Weak::upgrade(&node.upper) {
                if Rc::ptr_eq(upper.lower.as_ref().unwrap(), &node) {
                    node = upper;
                    i += 1;
                } else {
                    break;
                }
            } else {
                break;
            }
        }

        //弹出空层: 每次删除只可能制造一个空层
        if !self.layers.is_empty() && 0 == get!(self.layers, self.layers.len() - 1).node_cnt {
            self.layers.pop();
        }

        Ok(())
    }

    /// 更新已有K的值
    pub fn update(&self, key: &K, value: V) -> Result<(), XErr> {
        let node = self.locate(key).map_err(XErr::from)?;
        chg!(@node, value, Rc::new(value));
        Ok(())
    }

    /// 据K获V
    pub fn get(&self, key: &K) -> Result<Rc<V>, XErr> {
        self.locate(key)
            .map(|n| Rc::clone(&n.value))
            .map_err(XErr::from)
    }

    //对于随机出来的数字,从最高位开始:
    //    - 单个bit为1的概率为1/(2^1),
    //    - 连续2个bit为1的概率为1/(2^2),
    //    - ...
    //    - 连续32个bit同时为1的概率为1/(2^32)
    //如此以来, 随机数的大小与其出现的概率便成负相关
    //- @unit_siz[in]: 层级跨度(可选值: 2 或 4)
    #[inline(always)]
    fn gen_height(&self, unit_siz: usize) -> usize {
        let n = random::<u128>();
        let mut i = 0usize;
        while 0 < (n & (1u128 << i)) {
            i += 1;
        }

        i /= unit_siz / 2;

        //max_height 从1开始
        if i >= self.max_height {
            self.max_height - 1
        } else {
            i
        }
    }

    //基于新节点, 为两侧的所有孤儿节点添加父节点信息
    #[inline(always)]
    fn upper_refresh(new: Rc<Node<K, V>>) {
        let mut raw;
        let mut l = Rc::clone(&new);
        let mut r = Rc::clone(&new);

        while let Some(left) = Weak::upgrade(&l.left) {
            if Weak::upgrade(&left.upper).is_none() {
                l = left;
                chg!(l, upper, Weak::clone(&new.upper), raw);
            } else {
                break;
            }
        }

        while let Some(right) = r.right.as_ref() {
            if Weak::upgrade(&right.upper).is_none() {
                r = Rc::clone(right);
                chg!(r, upper, Weak::clone(&new.upper), raw);
            } else {
                break;
            }
        }
    }

    /// 获取K所在节点
    fn locate(&self, key: &K) -> Result<Rc<Node<K, V>>, ZErr<K, V>> {
        let mut cursor = if !self.layers.is_empty() {
            Rc::clone(&get!(self.layers, self.layers.len() - 1).head)
        } else {
            return Err(ZErr::NotExists(None));
        };

        if *key == *cursor.key {
            return Ok(cursor);
        }

        'outer: loop {
            if *key > *cursor.key {
                while let Some(right) = cursor.right.as_ref() {
                    if *key == *right.key {
                        return Ok(Rc::clone(right));
                    } else if *key > *right.key {
                        cursor = Rc::clone(right);
                        continue;
                    } else if let Some(lower) = right.lower.as_ref() {
                        cursor = Rc::clone(lower);
                        continue 'outer;
                    } else {
                        return Err(ZErr::NotExists(Some(cursor)));
                    }
                }

                if let Some(lower) = cursor.lower.as_ref() {
                    cursor = Rc::clone(lower);
                } else {
                    return Err(ZErr::NotExists(Some(cursor)));
                }
            } else {
                while let Some(left) = Weak::upgrade(&cursor.left) {
                    if *key == *left.key {
                        return Ok(left);
                    } else if *key < *left.key {
                        cursor = left;
                        continue;
                    } else if let Some(lower) = left.lower.as_ref() {
                        cursor = Rc::clone(lower);
                        continue 'outer;
                    } else {
                        return Err(ZErr::NotExists(Some(cursor)));
                    }
                }

                if let Some(lower) = cursor.lower.as_ref() {
                    cursor = Rc::clone(lower);
                } else {
                    return Err(ZErr::NotExists(Some(cursor)));
                }
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use rand::Rng;

    fn gen_sample(total: u32) -> Vec<Box<[i128]>> {
        let mut rng = rand::thread_rng();
        let mut sample = vec![];
        let mut v;

        for _ in 0..total {
            v = vec![];
            (0..100).for_each(|_| v.push(rng.gen::<i128>()));
            sample.push(v.into_boxed_slice());
        }

        sample.sort();
        sample.dedup();
        sample
    }

    fn function_test(sample: &[Box<[i128]>], max_height: usize, unit_siz: usize) {
        let mut sl = SkipList::new(max_height, unit_siz);

        sample.iter().for_each(|i| sl.put(i, i[0]).unwrap());
        assert!(1 <= sl.layers.len());

        sl.layers.iter().for_each(|layer| {
            assert!(Weak::upgrade(&layer.head.left).is_none());
            let mut n = Rc::clone(&layer.head);
            let mut cnt = 1;
            while let Some(right) = n.right.as_ref() {
                cnt += 1;
                n = Rc::clone(right);
            }
            assert_eq!(layer.node_cnt, cnt);
        });

        sample.iter().for_each(|i| {
            assert_eq!(i[0], *sl.get(&i).unwrap());
            sl.update(&i, i[1]).unwrap();
            assert_eq!(i[1], *sl.get(&i).unwrap());
            sl.del(&i).unwrap();
            assert!(sl.get(&i).is_err());
        });

        assert!(sl.layers.is_empty());
    }

    #[test]
    fn entry() {
        let sample;
        if cfg!(debug_assertions) {
            sample = gen_sample(100);
        } else {
            sample = gen_sample(10000);
        };

        (8..128).step_by(2).for_each(|max_height| {
            [2, 4].iter().cloned().for_each(|unit_siz| {
                function_test(&sample, max_height, unit_siz);
            });
        });
    }
}
